A Stack Algorithm for Faster Sequential Decoding of Transmitted Information

In this paper a new Sequential Decoding algorithm is developed as a heuristically natural way of taking advantage of tree structure of codes. no previous knowledge of encoding is assumed. Our algorithm utilizes stack storage. It is much simpler to describe and analyze than the Fano algorithm, and is about six times faster than the latter at transmission rates equal to R_comp. Bounds on probability of error and on the average number of decoding steps are derived from scratch by previously known methods. Practical problems connected with instrumenting the stack algorithm are discusses and a scheme is described facilitating satisfactory performance even with limited stack storage capacity. Preliminary simulation results are presented estimating the decoding effort and the needed stack size.